package com.hyb.algorithm.data.struct.dp;

/**
 *
 *    213. 打家劫舍 II
 *    https://leetcode.cn/problems/house-robber-ii/description/
 *
 * @author: ybhu
 * @create: 2024/01/05 11:35
 */
public class Rob4 {

    public static void main(String[] args) {
        int[] nums={1,2,1,1};
        int ret=new Rob4().rob(nums);

        System.out.println(ret);
    }

    public int rob(int[] nums) {
        int n=nums.length;

        //边界处理
        if(n==0){
            return 0;
        }

        if(n==1){
            return nums[0];
        }


        //边界处理
        if(n==2){
            return Math.max(nums[0],nums[1]);
        }

        //如果偷nums[0] 那么结果为 num[0]....nums[n-2]
        int ret1=rob(nums,0,n-2);
        //如果不偷num[0] 那么结果为 num[1]....num[n-1]
        int ret2=rob(nums,1,n-1);

        return Math.max(ret1,ret2);

    }


    public int rob(int[] nums,int start,int end){

        if(end-start==0){
            return nums[start];
        }

        int[] memo=new int[end-start+1];
        memo[0]=nums[start];
        memo[1]=Math.max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++){
            memo[i-start]=Math.max(memo[i-start-1],memo[i-start-2]+nums[i]);
        }

        return memo[end-start];
    }
}
